package HashTable;

import java.util.HashMap;
import java.util.Map;

public class _525_ContiguousArray {
    //over time limited
    public int findMaxLength_0(int[] nums) {
        int len = nums.length;
        int[] ones = new int[len + 1];
        int[] zeros = new int[len + 1];
        int one = 0, zero = 0;
        //count every one and zero
        zeros[0] = 0;
        ones[0] = 0;
        for (int i = 1; i <= len; i++) {
            if (nums[i - 1] == 1) {
                one++;
            } else {
                zero++;
            }
            zeros[i] = zero;
            ones[i] = one;
        }
        int max = 0;
        //slide window size
        for (int i = 2; i <= len; i += 2) {
            for (int j = i; j <= len; j++) {
                if (zeros[j] - zeros[j - i] == ones[j] - ones[j - i]) {
                    max = i;
                    break;
                }
            }
        }
        return max;
    }

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> maps = new HashMap<>();
        maps.put(0, 0);
        int count = 0, max = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 1 ? 1 : -1);
            if (maps.containsKey(count)) {
                max = Math.max(max, i - maps.get(count));
            } else {
                maps.put(count, i);
            }
        }
        return max;
    }
}
